Topology sensing is crucial for proper link setup as well as routing in a wireless communications network. The problem becomes more difficult to solve when communicating nodes are mobile, as in such cases, link conditions as well as node locations are continuously varying with time. Hence, a robust algorithm is needed in order to establish good links among communicating nodes and at the same time maintain a relatively stable topology. Otherwise, links will be established/torn-down very rapidly and routing, which is fundamentally based on topology configuration, becomes very difficult to handle and routing convergence becomes a serious problem, if not infeasible.
Consider a wireless network with a highly dynamic topology with mobile network nodes and mobile subscribers. The nodes are connected to one or more of their neighbors via point to point wireless links, thus providing backbone connectivity that extends over the service area of the network. The network nodes also provide wireless access to the mobile subscribers which can setup multimedia calls with other subscribers within the network or outside of the network. By way of one example, such a network is described in U.S. patent applications identified by Ser. No. 09/191,133 (entitled: “Subnetwork Layer for a Multimedia Mobile Network”); Ser. No. 09/191,132 (entitled: “Addressing Scheme for a Multimedia Mobile Network”); and Ser. No. 09/191,134 (entitled: “Mobility Management for a Multimedia Mobile Network”), all concurrently filed on Nov. 13, 1998, the disclosures of which are incorporated by reference herein. Given the mobility of both the subscriber terminals and the network nodes, implementation of a topology sensing methodology for use in such a network raises one or more of the issues mentioned above.
There are various topology sensing methodologies known in the communications prior art. For example, typical cellular/PCS networks implement a form of topology sensing wherein network nodes, i.e., base stations, transmit pilot signals to subscriber terminals. However, in a cellular/PCS network, only subscriber terminals are mobile while network nodes or base stations are static. Thus, any topology sensing is concerned only with the mobility of the subscribers and thus no provision is made for the mobility of a base station.
The DARPA Packet Radio Network (PRNET) is a kind of a mobile ad-hoc radio network in which network nodes are mobile and use the wireless radio medium to communicate with one another. The network nodes use a hop-by-hop packet forwarding mechanism to carry traffic from the source node to the destination if the source and destination cannot “hear” each other. The network topology is constantly changing so that the network nodes need to keep track of this dynamically changing topology in order to be able to direct traffic to the correct destinations. A PRNET employs the following mechanism to keep track of the changing topology and to provide end-to-end connectivity in the network. Nodes in a PRNET have a common channel that is used by all nodes to carry user traffic as well as to announce their presence through the transmission of some special packets. Each node periodically transmits these special packets on that channel which is typically supported by an omni-directional antenna. The protocol for transmitting these special packets as well as user packets is “carrier sense multiple access” in which nodes attempt to transmit packets only after sensing that the carrier (channel) is idle. Even then, there is a random wait period which is intended to reduce the probability of multiple nodes transmitting their packets simultaneously after the channel becomes idle. PRNET is further described in J. Jubin et al., “The DARPA Packet Radio Network Protocols,” Proceedings of IEEE, vol. 75, no. 1, January 1987, the disclosure of which is incorporated herein by reference.
While the scheme employed in PRNET, to enable network nodes to announce their presence and sense the presence of their neighbors, does its job, it is not particularly efficient or well suited to highly mobile networks where nodes are interconnected with high speed point-to-point links supported by steerable directional antennas. Also, the PRNET makes no provision for changing channels specifically to avoid collision of the special packets associated with its topology sensing mechanism.
Therefore, there is a need for methods and apparatus for topology sensing in a communications network including mobile network nodes which eliminate or at least reduce the effects associated with the shortcomings of the prior art as discussed above and which otherwise exist in the art.